//给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。 
//
// 字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。 
//
// 说明： 
//
// 
// 字母异位词指字母相同，但排列不同的字符串。 
// 不考虑答案输出的顺序。 
// 
//
// 示例 1: 
//
// 
//输入:
//s: "cbaebabacd" p: "abc"
//
//输出:
//[0, 6]
//
//解释:
//起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
//起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
// 
//
// 示例 2: 
//
// 
//输入:
//s: "abab" p: "ab"
//
//输出:
//[0, 1, 2]
//
//解释:
//起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
//起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
//起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。
// 
// Related Topics 哈希表 
// 👍 486 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ConcurrentSkipListMap;

//Java：找到字符串中所有字母异位词
public class P438FindAllAnagramsInAString{
    public static void main(String[] args) {
        Solution solution = new P438FindAllAnagramsInAString().new Solution();
        String s = "cbaebabacd";
        String p = "abc";
        List<Integer> res = solution.findAnagrams(s,p);
        System.out.println(res);
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        char[] arrS = s.toCharArray();//cbaebabacd
        char[] arrP = p.toCharArray();//abc

        // 接收最后返回的结果
        List<Integer> ans = new ArrayList<>();

        // 定义一个 needs 数组来看 arrP 中包含元素的个数
        ConcurrentSkipListMap<Character, Integer> needs = new ConcurrentSkipListMap<>();
        // 定义一个 window 数组来看滑动窗口中是否有 arrP 中的元素，并记录出现的个数
        ConcurrentSkipListMap<Character, Integer> window = new ConcurrentSkipListMap<>();

        // 先将 arrP 中的元素保存到 needs 数组中
        for (int i = 0; i < arrP.length; i++) {
            needs.put(arrP[i], 1);
        }

        // 定义滑动窗口的两端
        int left = 0;
        int right = 0;
        int match = 0;
        // 右窗口开始不断向右移动
        while (right < arrS.length) {
            right++;
            // 将右窗口当前访问到的元素 curR 个数加 1
            window.put(arrS[right], 1);
            //判断是否形同
            if(window.get(arrS[right]).equals(needs.getOrDefault(arrS[right], null))){
                match++;
            }
            // 当 window 数组中 curR 比 needs 数组中对应元素的个数要多的时候就该移动左窗口指针
            while (window.size() > needs.size()) {
                left++;
                // 将左窗口当前访问到的元素 curL 个数减 1
                window.remove(arrS[left]);
            }

            // 这里将所有符合要求的左窗口索引放入到了接收结果的 List 中
            if (match == arrP.length) {
                ans.add(left);
                match = 0;
            }
        }
        return ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
